package core;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;

import org.apache.commons.lang3.SerializationUtils;

import util.IO;

public class QAP {
	public static Solution bestSolution = null;
	public static double bestCost = Double.MAX_VALUE;
	static double bestLocalCost = Double.MAX_VALUE;
	
	public static Solution DoQAP(String pathFile, int numIterations, int rclCount, double alpha){
		//pegar solu��o inicial
		final Solution initialSolution = IO.Read(pathFile);
		initialSolution.setCost(EvaluateSolution(initialSolution));
	
		for (int i = 0; i < numIterations; i++) {
			//construcao gulosa
			Solution newSolution = DoGreedyConstruction(initialSolution, rclCount, alpha);
			
			//fazer busca local
			newSolution = DoLocalSearch(newSolution);
			
			//verificar se � a melhor solucao
			if(newSolution.getCost() < bestCost){
				bestSolution = newSolution;
				bestCost = newSolution.getCost();
				System.out.println(i+": "+bestCost);
			}
			
			//Maximizar o bestLocalCost
			bestLocalCost = Double.MAX_VALUE;
		}
		
		return bestSolution;
	}
	
	private static Solution DoGreedyConstruction(Solution initialSolution, int rclCount, double alpha){
		//gerar RCL
		ArrayList<Solution> listSolution = DoRCL(initialSolution, rclCount, alpha);
		
		//escolher um elemento aleatoriamente
		Random r = new Random();
		int choice = r.nextInt(listSolution.size());
		Solution solution = listSolution.get(choice);
		
		//retornar elemento		
		return solution;
	}
	
	private static Solution DoLocalSearch(Solution newSolution){
		ArrayList<Solution> listLocalSolutions = new ArrayList<Solution>();
		boolean continueToSearch = false;
		
		//fazer busca em profundidade
		ArrayList<Pair> pairs = MakePairs(newSolution);
		Solution localSolution = null;
		for (int i = 0; i < pairs.size(); i++) {
			//localSolution = newSolution;
			localSolution = (Solution) SerializationUtils.clone(newSolution); //Clona a solucao, sem referencia
			localSolution = Do2Troca(pairs.get(i), localSolution);
			localSolution.setCost(EvaluateSolution(localSolution));
			listLocalSolutions.add(localSolution);
		}
		
		//selecionar melhor local
		for (int i = 0; i < listLocalSolutions.size(); i++) {
			if(listLocalSolutions.get(i).getCost() < bestLocalCost){
				bestLocalCost = listLocalSolutions.get(i).getCost();
				localSolution = listLocalSolutions.get(i);
				continueToSearch = true;
			}
		}
		
		if(continueToSearch){
			//System.out.println(localSolution.PrintPermutation()+"\n");
			localSolution = DoLocalSearch(localSolution);
		}

		return localSolution;
	}
	
	private static ArrayList<Solution> DoRCL(Solution initialSolution, int rclCount, double alpha){
		ArrayList<Solution> listSolution = new ArrayList<Solution>();
		ArrayList<Pair> pairs = new ArrayList<Pair>();
		
		pairs = MakePairs(initialSolution);

		Solution sol = null;
		for (int i = 0; i < pairs.size(); i++) {
			sol = (Solution) SerializationUtils.clone(initialSolution); //Clona a solucao, sem referencia
			sol = Do2Troca(pairs.get(i), sol);
			sol.setCost(EvaluateSolution(sol));
			listSolution.add(sol);
		}
		
		//calcular numero de solucoes que serao retornados
		int countSolutions = (int) (alpha*rclCount);
		
		//ordenar crescentemente as solucoes
		Collections.sort(listSolution, new Comparator<Solution>() {
			public int compare(Solution o1, Solution o2) {
				if(o1.getCost() > o2.getCost()){
					return 1;
				}else if(o1.getCost() < o2.getCost()){
					return -1;
				}else{
					return 0;
				}
			}
		});
		
		//escolher quais solucoes vao para proxima fase
		ArrayList<Solution> list = new ArrayList<Solution>();
		
		for (int i = 0; i < countSolutions; i++) {
			list.add(listSolution.get(i));
		}
		
		return list;
	}
	
	private static Solution Do2Troca(Pair pair, Solution sol){				
		//trocar linha
		sol.ChangeDestinationLine(pair.getFirst(), pair.getSecond());
		//trocar coluna
		sol.ChangeDestinationColumn(pair.getFirst(), pair.getSecond());		
		//trocar atributo de permutacao
		int firstElement = sol.getPermutationElement(pair.getFirst());
		int secondElement = sol.getPermutationElement(pair.getSecond());
		
		sol.setPermutationElement(pair.getFirst(), secondElement);
		sol.setPermutationElement(pair.getSecond(), firstElement);
	
		return sol;
	}
	
	private static ArrayList<Pair> MakePairs(Solution initialSolution){
		int[] per = initialSolution.getPermutation();
		ArrayList<Pair> pairs = new ArrayList<Pair>();
		
		//ex: [1 2 3 4] -> randomizar e trocar 2 posicoes
		
		
		for (int i = 0; i < per.length; i++) {
			for (int j = i+1; j < per.length; j++) {
				pairs.add(new Pair(i, j));
			}
		}
		
		return pairs;
	}
	
	private static double EvaluateSolution(Solution arrayMatrix) {
		int tam = arrayMatrix.getFlux().length;

		double temp = 0;
		for (int i = 0; i < tam; i++) {
			for (int j = 0; j < tam; j++) {
				if (j > i) {
					// resultado += fluxo (ij) * distancia (pi[i] pi[j])
					// quando j > i
					temp += arrayMatrix.getFlux()[i][j]
							* arrayMatrix.getDestination()[i][j];
				}
			}
		}

		return temp;

	}
	
	//Metodos auxiliares
	public static void PrintMatrix(int[][] matrix, String title){
		System.out.println("\n"+title);
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix.length; j++) {
				System.out.print(matrix[i][j]+"\t");
			}
			System.out.println();
		}
	}
	
}
